package leetcode.D800.T712;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-20 22:12:18 星期日
 */

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int[] dp = new int[s2.length()+1];
        for(int i=1; i<dp.length; ++i) {
            dp[i] = dp[i-1] + s2.charAt(i-1);
        }
        for(int i=0; i<s1.length(); ++i) {
            int last = dp[0];
            dp[0] += s1.charAt(i);
            for(int j=0; j<s2.length(); ++j) {
                if(s1.charAt(i) == s2.charAt(j)) {
                    int temp = last;
                    last = dp[j+1];
                    dp[j+1] = temp;
                } else {
                    last = dp[j+1];
                    dp[j+1] = Math.min(dp[j]+s2.charAt(j), dp[j+1]+s1.charAt(i));
                }
            }
        }
        return dp[dp.length-1];
    }
}
